package Aula18;

import java.util.Random;

public class SkipList {

	private final static int MAX_LEVEL = 10;
	private final float PROB = 0.5f;
	private int level;
	private final NoSkip raiz = new NoSkip(-1, MAX_LEVEL);

	public SkipList() {
		level = 0;
	}

	private int randomLevel() {
		Random r = new Random();
		int v = 1;
		while (r.nextFloat() < PROB && v < MAX_LEVEL)
			v++;
		return v;

	}
	
	public int insert(int key){
		if(key < 0){
			return -1;
		}
		NoSkip update[] = new NoSkip[MAX_LEVEL + 1];
		NoSkip x = raiz;
		for (int i = level; i >= 0; i--) {
			while (x.forward[i] != null && x.forward[i].key < key)
				x = x.forward[i];
			update[i] = x;
		}
		x = x.forward[0];
		if (x == null || x.key != key){
			int lvl = randomLevel();
			
			if (lvl > level) {
			    for (int i = level + 1; i <= lvl; i++) {
			        update[i] = raiz;
			    }
			    level = lvl;
			}
			
			x = new NoSkip(key, lvl);
			for (int i = 0; i <= lvl; i++) {
			    x.forward[i] = update[i].forward[i];
			    update[i].forward[i] = x;
			}
			return 1;
		}
		return 0;
	}

	public int search(int key) {
		if(key < 0){
			return -1;
		}
		NoSkip x = raiz;
		for (int i = level; i >= 0; i--) {
			while (x.forward[i] != null && x.forward[i].key < key)
				x = x.forward[i];
		}
		x = x.forward[0];
		if (x != null && x.key == key)
			return 1;
		return 0;
	}
}
